339. Nested List Weight Sum
Medium

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

Example 3:

Input: nestedList = [0]
Output: 0

 

Constraints:

  • 1 <= nestedList.length <= 50
  • The values of the integers in the nested list is in the range [-100, 100].
  • The maximum depth of any integer is less than or equal to 50.
Accepted
128,735
Submissions
166,425
Seen this question in a real interview before?
Companies

Average Rating: 4.86 (71 votes)

Premium

Video Solution


 

Solution Article


Because the input is nested, it is natural to think about the problem in a recursive way. We go through the list of nested integers one by one, keeping track of the current depth dd. If a nested integer is an integer, nn, we calculate its sum as n×dn\times d. If the nested integer is a list, we calculate the sum of this list recursively using the same process but with depth equals d+1d + 1.

Implementation

Complexity Analysis

Let NN be the total number of nested elements in the input list. For example, the list [ [[[[1]]]], 2 ] contains 44 nested lists and 22 nested integers (11 and 22), so N=6N = 6 for that particular case.

  • Time complexity : O(N)\mathcal{O}(N).

    Recursive functions can be a bit tricky to analyze, particularly when their implementation includes a loop. A good strategy is to start by determining how many times the recursive function is called, and then how many times the loop will iterate across all calls to the recursive function.

    The recursive function, dfs(...) is called exactly once for each nested list. As NN also includes nested integers, we know that the number of recursive calls has to be less than NN.

    On each nested list, it iterates over all of the nested elements directly inside that list (in other words, not nested further). As each nested element can only be directly inside one list, we know that there must only be one loop iteration for each nested element. This is a total of NN loop iterations.

    So combined, we are performing at most 2N2 \cdot N recursive calls and loop iterations. We drop the 22 as it is a constant, leaving us with time complexity O(N)\mathcal{O}(N).

  • Space complexity : O(N)\mathcal{O}(N).

    In terms of space, at most O(D)O(D) recursive calls are placed on the stack, where DD is the maximum level of nesting in the input. For example, D=2D=2 for the input [[1,1],2,[1,1]], and D=3D=3 for the input [1,[4,[6]]].

    In the worst case, D=ND = N, (e.g. the list [[[[[[]]]]]]) so the worst-case space complexity is O(N)O(N).



We can also solve the problem using a breadth-first search. The algorithm for this is closely based on the standard breadth-first search template. The algorithm fully processes each depth before moving to the next one.

Implementation

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N).

    Similar to the DFS approach. Each nested element is put on the queue and removed from the queue exactly once.

  • Space complexity : O(N)\mathcal{O}(N).

    The worst-case for space complexity in BFS occurs where most of the elements are in a single layer, for example, a flat list such as [1, 2, 3, 4, 5] as all of the elements must be put on the queue at the same time. Therefore, this approach also has a worst-case space complexity of O(N)\mathcal{O}(N).

Report Article Issue

Comments: 27
miaoyao's avatar
Read More

BFS:

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        Queue<NestedInteger> q = new LinkedList<>();
        for(NestedInteger n : nestedList){
            q.add(n);
        }
        int deep = 1;
        int ans = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                NestedInteger temp = q.poll();
                if(temp.isInteger()){
                    ans += deep * temp.getInteger();
                }else{
                    for(NestedInteger n : temp.getList()){
                        q.add(n);
                    }
                }
            }
            deep++;
        }
        return ans;
    }
}

DFS:

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }
    public int dfs(List<NestedInteger> nestedList, int deep){
        int ans = 0;
        for(NestedInteger n : nestedList){
            if(n.isInteger()) ans += (deep * n.getInteger());
            else  ans += dfs(n.getList(), deep + 1);
        }
        return ans;
    }
}

14
Show 2 replies
Reply
Share
Report
fgalindo's avatar
Read More

Python recursive solution

class Solution(object):
	def depthSum(self, nestedList):
		"""
		:type nestedList: List[NestedInteger]
		:rtype: int
		"""
		
		return self.recSum(nestedList, 1)
		
		
		
	def recSum(self, nestedList, depth):
		
		sum = 0
		
		for item in nestedList:
			
			if item.isInteger():
				
				sum += (item.getInteger() * depth)
				
			else:
				sum += self.recSum(item.getList(), depth+1)
				
				
		return sum

6
Show 1 reply
Reply
Share
Report
tkblackbelt's avatar
Read More

Python DFS

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        
        if not nestedList: return 0
        
        total = 0
        stack = [(l, 1) for l in nestedList]
        
        while stack:
            l, index = stack.pop()
            
            value = l.getInteger()
            
            if value is not None:
                total += value * index
            else:
                for item in l.getList():
                    stack.append((item, index + 1))
        
        return total

6
Reply
Share
Report
hero_afei's avatar
Read More

My non recursive solution:
public class Solution {
public int depthSum(List nestedList) {
int ans = 0, depth = 1;
Queue<List> queue = new LinkedList<>();
queue.offer(nestedList);
queue.offer(null);
while(!queue.isEmpty()){
List t = queue.poll();
if(t == null){
depth ++;
if(!queue.isEmpty())
queue.offer(null);
continue;
}
for(NestedInteger n : t){
if(n.isInteger()){
ans = ans + depth * n.getInteger();
}else{
queue.offer(n.getList());
}
}
}
return ans;
}
}

3
Reply
Share
Report
Mrmagician's avatar
Read More

My iterative solution:

stack = [[1, nestedList]]
        count = 0
        while len(stack):
            weight, nest = stack.pop()
            for i in nest:
                if i.isInteger():
                    count += i.getInteger() * weight
                else:
                    stack.append([weight + 1, i.getList()])
            
        return count

1
Reply
Share
Report
zabrosov's avatar
Read More

class Solution(object):
    def depthSum(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        def lfunc(nestedList, l, res):
            for x in nestedList:
                if x.isInteger():
                    n = x.getInteger()
                    res += n * l
                else:
                    res += lfunc(x.getList(), l + 1, 0)
            return res
        return lfunc(nestedList, 1, 0)

1
Reply
Share
Report
YoghurtBoy's avatar
Read More

iterative... even slow
cpp:

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        int res = 0;
        int level = 1;
        while (!nestedList.empty()) {
            vector<NestedInteger> nextLevel;
            for (auto n : nestedList) {
                if (n.isInteger())
                    res += n.getInteger() * level;
                else
                    nextLevel.insert(nextLevel.end(), n.getList().begin(), n.getList().end());
            }
            nestedList = nextLevel;
            level++;
        }
        return res;
    }
};

Java:

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int res = 0;
        int level = 1;
        while (!nestedList.isEmpty()) {
            List<NestedInteger> nextLevelList = new LinkedList<>();
            for (NestedInteger nestedInteger : nestedList) {
                if (nestedInteger.isInteger()) {
                    res += nestedInteger.getInteger() * level;
                } else {
                    nextLevelList.addAll(nextLevelList.size(), nestedInteger.getList());
                }
            }
            nestedList = nextLevelList;
            level++;
        }
        return res;
    }
}

1
Reply
Share
Report
mian_hashim's avatar
Read More

Can't we use BFS in this problem? Since technically this is a level order traversal?

1
Show 3 replies
Reply
Share
Report
luv_ahuja4's avatar
Read More

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    int sum = 0;
    public int depthSum(List<NestedInteger> nestedList) {        
        maxDepth(nestedList,1);
        return sum;        
    }
    
    
    public void maxDepth(List<NestedInteger> ni,int i){
        
        for (NestedInteger n : ni){            
            if (n.isInteger()){
                sum=sum+n.getInteger()*i;
            }else {
                maxDepth(n.getList(),i+1);
            }                        
        }                        
    }        
}

1
Reply
Share
Report
jiangyucara's avatar
Read More

Can anyone explain why do we do the method overload here?

0
Show 3 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/16/2021 09:20Accepted0 ms10 MBcpp
06/16/2021 09:19Accepted0 ms9.4 MBcpp
06/16/2021 09:16Accepted4 ms9.9 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.